package NiuKe.JianZhiOffer;

/**
 * 描述
 * 输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构）
 * 示例1
 * 输入：
 * {8,8,#,9,#,2,#,5},{8,9,#,2}
 *
 * 返回值：
 * true
 */
public class JZ17 {

    public class Solution {
        public boolean HasSubtree(TreeNode root1,TreeNode root2) {
            if(root2 == null || root1 == null)return false;

            if(root1.val == root2.val){
                if(check( root1, root2)){
                    return true;
                }else{
                    if(HasSubtree(root1.left,root2) || HasSubtree(root1.right,root2)){
                        return true;
                    }
                }
            }else{
                return HasSubtree(root1.left,root2) || HasSubtree(root1.right,root2);
            }
            return false;

        }

        public boolean check(TreeNode root1,TreeNode root2) {
            boolean left = false;
            boolean right = false;
            if(root1.val == root2.val){
                if(root2.left == null){left = true;}else{
                    if(root1.left == null){left = false;}else{
                        left = check(root1.left,root2.left);
                    }
                }
                if(root2.right == null){right = true;}else{
                    if(root1.right == null ){right =false;}else{
                        right = check(root1.right,root2.right);
                    }
                }
            }
            return left && right;
        }

    }
}
